#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>

using namespace std;

// Define a struct to represent a movie
struct Movie {
    int start_time;
    int end_time;
    int category;
};

int main() {
    // Start the timer
    auto startTime = chrono::steady_clock::now();

    int num_movies, num_categories;
    cin >> num_movies >> num_categories;

    // Read the category limits into a vector
    vector<int> category_limit(num_categories + 1);
    for (int i = 1; i <= num_categories; i++) {
        cin >> category_limit[i];
    }

    // Read the movie information into a vector
    vector<Movie> movies(num_movies);
    for (int i = 0; i < num_movies; i++) {
        cin >> movies[i].start_time >> movies[i].end_time >> movies[i].category;
        if (movies[i].end_time < movies[i].start_time) {
            movies[i].end_time = 24;
        }

        if (movies[i].end_time == movies[i].start_time) {
            movies[i].end_time += 1;
        }
    }

    // Sort the movies by end time
    sort(movies.begin(), movies.end(), [](const Movie& a, const Movie& b) {
        if (a.end_time == b.end_time) { return a.start_time < b.start_time; }
        return a.end_time < b.end_time;
    });

    // // Sort the movies by start time
    // sort(movies.begin(), movies.end(), [](const Movie& a, const Movie& b) {
    //     return a.start_time < b.start_time;
    // });

    // Define a bitset to represent the availability of each hour of the day
    bitset<24> hours;

    // Keep track of how many movies of each category have been watched
    vector<int> num_watched(num_categories + 1, 0);

    // Keep track of the indices of the watched movies
    vector<int> watched;

    int time_watched = 0;

    // Iterate over the movies and check if each movie can be watched
    for (int i = 0; i < num_movies; i++) {
        const Movie& movie = movies[i];

        // Check if any hour of the movie overlaps with an already watched movie
        bool can_watch = true;
        for (int hour = movie.start_time; hour < movie.end_time; hour++) {
            if (hours[hour]) {
                can_watch = false;
                break;
            }
        }
        if (hours[movie.start_time]) { can_watch = false; }

        // If the movie can be watched and its category limit has not been reached,
        // mark the hours as watched, add the movie to the list of watched movies,
        // and print the start time, end time, and category of the movie
        if (can_watch && num_watched[movie.category] < category_limit[movie.category]) {
            num_watched[movie.category]++;
            time_watched += movie.end_time - movie.start_time;
            watched.push_back(i);
            hours[movie.start_time] = true;
            for (int hour = movie.start_time; hour < movie.end_time; hour++) {
                hours[hour] = true;
            }
            cout << movie.start_time << " " << movie.end_time << " " << movie.category << endl;
        }
    }

    // Output the number of watched movies
    cout << "\nNúmero de filmes: " << watched.size() << endl;
    cout << "Tempo de tela (em horas): " << time_watched << endl;

    // Calculate the time elapsed during algorithm execution
    auto endTime = chrono::steady_clock::now();
    double duration = chrono::duration_cast<chrono::microseconds>(endTime - startTime).count();

    cout << fixed;
    cout << "Time elapsed during the greedy algorithm (in microseconds): " << duration << endl;
    cout << scientific;

    return 0;
}

#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>

using namespace std;

// Define a struct to represent a movie
struct Movie {
    int start_time;
    int end_time;
    int category;
};

bool check_can_watch(const Movie& movie, const bitset<24>& hours, const vector<int>& num_watched, const vector<int>& category_limit) {
    if (num_watched[movie.category] >= category_limit[movie.category]) { return false; }
    for (int hour = movie.start_time; hour < movie.end_time; hour++) {
        if (hours[hour]) {
            return false;
        }
    }
    if (hours[movie.start_time]) { return false; }
    return true;
}

int main() {
    // Start the timer
    auto startTime = chrono::steady_clock::now();

    srand((unsigned) time(NULL));
    int num_movies, num_categories;
    cin >> num_movies >> num_categories;

    // Read the category limits into a vector
    vector<int> category_limit(num_categories + 1);
    for (int i = 1; i <= num_categories; i++) {
        cin >> category_limit[i];
    }

    // Read the movie information into a vector
    vector<Movie> unwatched_movies(num_movies);
    for (int i = 0; i < num_movies; i++) {
        cin >> unwatched_movies[i].start_time >> unwatched_movies[i].end_time >> unwatched_movies[i].category;
        if (unwatched_movies[i].end_time < unwatched_movies[i].start_time) {
            unwatched_movies[i].end_time = 24;
        }

        if (unwatched_movies[i].end_time == unwatched_movies[i].start_time) {
            unwatched_movies[i].end_time += 1;
        }
    }

    vector<Movie> watched_movies;
    vector<Movie> lost_movies;

    // Sort the movies by end time
    sort(unwatched_movies.begin(), unwatched_movies.end(), [](const Movie& a, const Movie& b) {
        if (a.end_time == b.end_time) { return a.start_time < b.start_time; }
        return a.end_time < b.end_time;
    });

    // Define a bitset to represent the availability of each hour of the day
    bitset<24> hours;

    // Keep track of how many movies of each category have been watched
    vector<int> num_watched(num_categories + 1, 0);

    int time_watched = 0;

    // Iterate over the movies and check if each movie can be watched
    while (!unwatched_movies.empty()) {
        bool end = false;
        Movie movie;
        int index;
        int random_num = rand() % 4;
        if (random_num != 0) {
            index = 0;
            movie = unwatched_movies.front();
        } else {
            index = rand() % unwatched_movies.size();
            movie = unwatched_movies[index];

            while(!check_can_watch(movie, hours, num_watched, category_limit)) {
                lost_movies.push_back(movie);
                unwatched_movies.erase(unwatched_movies.begin() + index);

                if (unwatched_movies.empty()) { end = true; break; }

                index = rand() % unwatched_movies.size();
                movie = unwatched_movies[index];
            }
        }

        if (end) { break; }

        if (check_can_watch(movie, hours, num_watched, category_limit)) {
            hours[movie.start_time] = true;
            for (int hour = movie.start_time; hour < movie.end_time; hour++) {
                hours[hour] = true;
            }
            num_watched[movie.category]++;
            time_watched += movie.end_time - movie.start_time;
            watched_movies.push_back(movie);
            unwatched_movies.erase(unwatched_movies.begin()+index);
            cout << movie.start_time << " " << movie.end_time << " " << movie.category << endl;
        } else {
            lost_movies.push_back(movie);
            unwatched_movies.erase(unwatched_movies.begin() + index);
        }
    }

    // Output the number of watched movies
    cout << "\nNúmero de filmes: " << watched_movies.size() << endl;
    cout << "Tempo de tela (em horas): " << time_watched << endl;

    // Calculate the time elapsed during algorithm execution
    auto endTime = chrono::steady_clock::now();
    double duration = chrono::duration_cast<chrono::microseconds>(endTime - startTime).count();

    cout << fixed;
    cout << "Time elapsed during the stochastic greedy algorithm (in microseconds): " << duration << endl;
    cout << scientific;

    return 0;
}


from os import listdir
from os.path import isfile, join

import pandas as pd
import plotly.graph_objects as go

import plotly.io as pio
pio.renderers.default='notebook'

files = [f for f in listdir("./outputs/greedy") if isfile(join("./outputs/greedy", f))]

num_movies = {}
screen_time = {}
execution_duration = {}

for file_name in files:
    num_movies[file_name] = {}
    screen_time[file_name] = {}
    execution_duration[file_name] = {}
    with open('./outputs/greedy/{}'.format(file_name), 'r') as f:
        lines = f.readlines()
        num_movies[file_name]['greedy'] = int(float(lines[-3].split()[-1]))
        screen_time[file_name]['greedy'] = int(float(lines[-2].split()[-1]))
        execution_duration[file_name]['greedy'] = int(float(lines[-1].split()[-1]))
        
        

    with open('./outputs/random/{}'.format(file_name), 'r') as f:
        lines = f.readlines()
        num_movies[file_name]['random'] = int(float(lines[-3].split()[-1]))
        screen_time[file_name]['random'] = int(float(lines[-2].split()[-1]))
        execution_duration[file_name]['random'] = int(float(lines[-1].split()[-1]))

num_movies_df = pd.DataFrame.from_dict(num_movies, 'index')
screen_time_df = pd.DataFrame.from_dict(screen_time, 'index')
execution_duration_df = pd.DataFrame.from_dict(execution_duration, 'index')


fig = go.Figure()
fig.add_trace(go.Bar(
    x=files,
    y=num_movies_df['greedy'],
    name='Greedy Algorithm',
    marker_color='indianred'
))
fig.add_trace(go.Bar(
    x=files,
    y=num_movies_df['random'],
    name='Stochastic Algorithm',
    marker_color='lightsalmon'
))

fig.update_layout(barmode='group', xaxis_tickangle=-45, title="Number of Movies")
fig.show()


fig = go.Figure()
fig.add_trace(go.Bar(
    x=files,
    y=screen_time_df['greedy'],
    name='Greedy Algorithm',
    marker_color='indianred'
))
fig.add_trace(go.Bar(
    x=files,
    y=screen_time_df['random'],
    name='Stochastic Algorithm',
    marker_color='lightsalmon'
))

fig.update_layout(barmode='group', xaxis_tickangle=-45, title="Total Screen Time")
fig.show()


fig = go.Figure()
fig.add_trace(go.Bar(
    x=files,
    y=execution_duration_df['greedy'],
    name='Greedy Algorithm',
    marker_color='indianred'
))
fig.add_trace(go.Bar(
    x=files,
    y=execution_duration_df['random'],
    name='Stochastic Algorithm',
    marker_color='lightsalmon'
))

fig.update_layout(barmode='group', xaxis_tickangle=-45, title="Execution Duration (microseconds)")
fig.show()

Relatório Parcial¶

Otimização de agendamento de filmes¶

Definição do Problema¶

Input¶

A Heurística Gulosa¶

Código fonte da heurística gulosa¶

Explicação do código fonte da heurística gulosa¶

A Heurística Aleatória¶

Código fonte da heurística aleatória¶

Explicação da heurística¶

Profiling com Valgrind¶

Profiling da heurística gulosa¶

Profiling da heurística aleatória¶

Conclusões sobre o profiling¶

Comparação de Resultados¶

Visualização comparativa entre a performance da heurística gulosa e aleatória¶

Conclusão dos resultados¶